#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : MinimumAbsoluteDifferenceBST.py
# @Time    : 2020/10/12 11:11
# @Description:
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        """
        Given a binary search tree with non-negative values, find the minimum absolute difference between values of
        any two nodes.

        Example:
        
            Input:

               1
                \
                 3
                /
               2

            Output:
            1

            Explanation:
                The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
         
        
        Note:
            There are at least two nodes in this BST.
            This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

        :param root:
        :return:
        """
        st = []
        p = root
        pre = - float('inf')
        min_val = float('inf')
        while p is not None or st:
            while p is not None:
                st.append(p)
                p = p.left
            p = st.pop()
            cur = p.val

            if cur - pre < min_val:
                min_val = cur - pre
            pre = cur
            p = p.right
        return min_val


if __name__ == '__main__':
    root = TreeNode(1)
    root.right = TreeNode(3)
    root.right.left = TreeNode(2)

    S = Solution()
    print(S.getMinimumDifference(root))
    print('done')
